#pragma once

#include <cstddef>
#include <utility>

#include "ezstl_allocator.hpp"
#include "ezstl_construct.hpp"
#include "ezstl_iterator_base.hpp"
#include "ezstl_vector.hpp"

namespace ezstl {

template <typename Value>
struct hashtable_node {
  hashtable_node *next;
  Value val;
};

template <typename Value, typename Key, typename HashFunc, typename ExtractKey,
          typename EqualKey, typename Alloc = Allocator<hashtable_node<Value>>>
class Hashtable;

template <typename Value, typename Key, typename HashFunc, typename ExtractKey,
          typename EqualKey, typename Alloc>
struct hashtable_iterator;

template <typename Value, typename Key, typename HashFunc, typename ExtractKey,
          typename EqualKey, typename Alloc>
struct hashtable_const_iterator;

template <typename Value, typename Key, typename HashFunc, typename ExtractKey,
          typename EqualKey, typename Alloc>
struct hashtable_iterator {
  using iterator_category = forward_iterator_tag;
  using value_type = Value;
  using difference_type = std::ptrdiff_t;
  using pointer = Value *;
  using reference = Value &;
  using size_type = std::size_t;

  using iterator =
      hashtable_iterator<Value, Key, HashFunc, ExtractKey, EqualKey, Alloc>;
  using const_iterator = hashtable_const_iterator<Value, Key, HashFunc,
                                                  ExtractKey, EqualKey, Alloc>;
  using hashtable =
      Hashtable<Value, Key, HashFunc, ExtractKey, EqualKey, Alloc>;
  using node = hashtable_node<Value>;

 protected:
  node *cur;
  hashtable *ht;

 public:
  hashtable_iterator() {}
  hashtable_iterator(node *n, hashtable *tab) : cur(n), ht(tab) {}

  reference operator*() const { return cur->val; }
  pointer operator->() const { return &(operator*()); }

  iterator &operator++() {
    const node *old = cur;
    cur = cur->next;  // 当前桶还有元素，直接返回
    if (!cur) {
      size_type bucket = ht->bkt_num(old->val);
      while (!cur && ++bucket < ht->buckets.size()) cur = ht->buckets[bucket];
    }
    return *this;
  }
  iterator operator++(int) {}
  bool operator==(const hashtable_iterator &other) const {
    return cur == other.cur;
  }
  bool operator!=(const hashtable_iterator &other) const {
    return !(*this == other);
  }
};

template <typename Value, typename Key, typename HashFunc, typename ExtractKey,
          typename EqualKey, typename Alloc>
struct hashtable_const_iterator {
  using iterator_category = forward_iterator_tag;
  using value_type = Value;
  using difference_type = std::ptrdiff_t;
  using pointer = const Value *;
  using reference = const Value &;
  using size_type = std::size_t;

  using iterator =
      hashtable_iterator<Value, Key, HashFunc, ExtractKey, EqualKey, Alloc>;
  using const_iterator = hashtable_const_iterator<Value, Key, HashFunc,
                                                  ExtractKey, EqualKey, Alloc>;
  using hashtable =
      Hashtable<Value, Key, HashFunc, ExtractKey, EqualKey, Alloc>;
  using node = hashtable_node<Value>;

  const node *cur;
  const hashtable *ht;

  hashtable_const_iterator() {}
  hashtable_const_iterator(const node *n, const hashtable *tab)
      : cur(n), ht{tab} {}
  hashtable_const_iterator(const iterator &other)
      : cur(other.cur), ht(other.ht) {}

  reference operator*() const { return cur->val; }
  pointer operator->() const { return &(operator*()); }
  const_iterator &operator++() {
    const node *old = cur;
    cur = cur->next;
    if (!cur) {
      size_type bucket = ht->bkt_num(old->val);
      while (!cur && ++bucket < ht->buckets.size()) cur = ht->buckets[bucket];
    }
    return *this;
  }
  const_iterator operator++(int) {
    const_iterator tmp = *this;
    ++*this;
    return tmp;
  }

  bool operator==(const const_iterator &it) const { return cur == it.cur; }
  bool operator!=(const const_iterator &it) const { return cur != it.cur; }
};

static const int __num_primes = 28;
static const std::size_t __prime_list[__num_primes] = {
    53,        97,         193,          389,         769,       1543,
    3079,      6151,       12289,        24593,       49157,     98317,
    196613,    393241,     786433,       1572869,     3145739,   6291469,
    12582917,  25165843,   50331653,     100663319,   201326611, 402653189,
    805306457, 1610612741, 3221225473ul, 4294967291ul};

/**
 * @brief 找到最接近并大于n的素数
 *
 * @param n
 * @return std::size_t
 */
inline std::size_t __next_prime(std::size_t n) {
  const std::size_t *first = __prime_list;
  const std::size_t *last = __prime_list + __num_primes;
  const std::size_t *pos = std::lower_bound(first, last, n);
  return (pos == last) ? *last : *pos;
}

inline std::size_t __max_buket_count() {
  return __prime_list[__num_primes - 1];
}

template <typename Value, typename Key, typename HashFunc, typename ExtractKey,
          typename EqualKey, typename Alloc>
class Hashtable {
 public:
  using value_type = Value;
  using key_type = Key;
  using size_type = std::size_t;
  using difference_type = std::ptrdiff_t;
  using pointer = value_type *;
  using const_pointer = const value_type *;
  using reference = Value &;
  using const_reference = const Value &;
  using allocator_type = Alloc;

  using hasher = HashFunc;
  using key_equal = EqualKey;
  using iterator =
      hashtable_iterator<Value, Key, HashFunc, ExtractKey, EqualKey, Alloc>;
  using const_iterator = hashtable_const_iterator<Value, Key, HashFunc,
                                                  ExtractKey, EqualKey, Alloc>;

 private:
  hasher hash;
  key_equal equals;
  ExtractKey get_key;

  using node = hashtable_node<Value>;

  ezstl::Vector<node *> buckets;
  size_type num_elements;

 public:
  Hashtable() : num_elements(0) { initialize_buckets(__prime_list[0]); }

  Hashtable(size_type n) : num_elements(0) { initialize_buckets(n); }

  Hashtable(size_type n, const HashFunc &hashf, const EqualKey &eql)
      : hash(hashf), equals(eql), get_key(ExtractKey()), num_elements(0) {
    initialize_buckets(n);
  }
  ~Hashtable() {
    clear();
  }

  iterator begin() {
    for (size_type i = 0; i < buckets.size(); i++)
      if (buckets[i]) return iterator{buckets[i], this};
    return end();
  }
  const_iterator begin() const {
    for (size_type i = 0; i < buckets.size(); i++)
      if (buckets[i]) return const_iterator{buckets[i], this};
    return end();
  }
  iterator end() { return iterator{0, this}; }
  const_iterator end() const { return const_iterator{0, this}; }

  iterator find(const key_type &key) {
    size_type n = bkt_num_key(key);
    node *first = 0;
    for (first = buckets[n]; first && !equals(get_key(first->val), key);
         first = first->next);
    return iterator{first, this};
  }

  const_iterator find(const key_type &key) const {
    size_type n = bkt_num_key(key);
    node *first = 0;
#if 0
    node *first = buckets[n];
    while (first && !equals(get_key(first->val), key)) {
      first = first->next;
    }
#endif
    for (first = buckets[n]; first && !equals(get_key(first->val), key);
         first = first->next);
    return const_iterator{first, this};  // 未找到返回 iterator{0, this} end()
  }

  size_type count(const key_type &key) const {
    const size_type n = bkt_num_key(key);
    size_type result = 0;
    for (const node *cur = buckets[n]; cur; cur = cur->next)
      if (equals(get_key(cur->val), key)) ++result;
    return result;
  }

  std::pair<iterator, bool> insert_unique(const_reference obj) {
    resize(num_elements + 1);  // 判断是否需要重建表格
    return insert_unique_noresize(obj);
  }

  iterator insert_equal(const_reference obj) {
    resize(num_elements + 1);
    return insert_equal_noresize(obj);
  }

  reference find_or_insert(const value_type &obj) {
    resize(num_elements + 1);
    size_type n = bkt_num(obj);
    node *first = buckets[n];
    for (first = buckets[n]; first; first = first->next)
      if (equals(get_key(first->val), get_key(obj))) return first->val;

    node *tmp = new_node(obj);
    tmp->next = buckets[n];
    buckets[n] = tmp;
    return tmp->val;
  }

  void resize(size_type num_elements_hint) {
    // 元素个数与bucket vector 的大小来比，如果前者大于后者，就重建表格
    // 由此可知 每个bucket(list) 的最大容量与buckets vector的大小相同
    const size_type old_n = buckets.size();
    if (num_elements_hint > old_n) {
      const size_type n = next_size(num_elements_hint);
      if (n > old_n) {
        ezstl::Vector<node *> tmp{n, (node *)0};
        try {
          // 处理每一个 bucket
          for (size_type bucket = 0; bucket < old_n; ++bucket) {
            node *first = buckets[bucket];
            while (first) {
              size_type new_bucket = bkt_num(first->val, n);
              // 令旧 bucket 指向当前串行的下一个节点
              buckets[bucket] = first->next;
              // 将当前节点的插入到新bucket中，成为第一个节点
              first->next = tmp[new_bucket];
              tmp[new_bucket] = first;
              // 回到旧bucket中，准备处理下一个节点
              first = buckets[bucket];
            }
          }
          buckets.swap(tmp);  // 交换 新旧bucket
          // 离开时释放tmp内存
        } catch (...) {
          throw;
        }
      }
    }
  }

  size_type erase(const key_type &key) {
    const size_type n = bkt_num_key(key);
    node *first = buckets[n];
    size_type erased = 0;

    if (first) {
      node *cur = first;
      node *next = cur->next;
      while (next) {  // 跳过first
        if (equals(get_key(next->val), key)) {
          cur->next = next->next;
          delete_node(next);
          next = cur->next;
          ++erased;
          --num_elements;
        } else {
          cur = next;
          next = cur->next;
        }
      }
      if (equals(get_key(first->val), key)) {
        buckets[n] = first->next;
        delete_node(first);
        ++erased;
        --num_elements;
      }
    }
    return erased;
  }

  void erase(const iterator &it) {
    node *p = it.cur;
    if (p) {
      const size_type n = bkt_num(p->val);
      node *first = buckets[n];

      if (first == p) {
        buckets[n] = first->next;
        delete_node(first);
        --num_elements;
      } else {
        node *cur = first;
        node *next = cur->next;
        while (next) {  // 寻找p前一个节点
          if (next == p) {
            cur->next = next->next;
            delete_node(next);
            --num_elements;
          } else {
            cur = next;
            next = cur->next;
          }
        }
      }
    }
  }

  void clear() {
    for (size_type i = 0; i < buckets.size(); ++i) {
      node *cur = buckets[i];
      while (cur) {
        node *next = cur->next;
        delete_node(cur);
        cur = next;
      }
      buckets[i] = 0;
    }
    num_elements = 0;
    // 并为删除 vector 空间
  }

  void copy_from(const Hashtable &other) {
    clear();
    buckets.clear();
    buckets.reserve(other.buckets.size());
    buckets.insert(buckets.end(), other.buckets.size(), (node *)0);
    try {
      for (size_type i = 0; i < other.buckets.size(); i++) {
        const node *cur = other.buckets[i];
        if (cur) {
          node *copy = new_node(cur->val);
          buckets[i] = copy;
          for (node *next = cur->next; next; cur = next, next = cur->next) {
            copy->next = new_node(next->val);
            copy = copy->next;
          }
#if 0
          node *next = cur->next;
          while (next) {
            copy->next = new_node(next->val);
            next = next->next;
          }
#endif
        }
      }
    } catch (...) {
      clear();
      throw;
    }
  }

  size_type size() const { return num_elements; }
  size_type max_size() const { return size_type(-1); }
  bool empty() const { return num_elements == 0; }

  size_type bucket_count() const { return buckets.size(); }

  size_type elems_in_bucket(size_type bucket) const {
    node *first = buckets[bucket];
    size_type count = 0;
    while (first) {
      ++count;
      first = first->next;
    }
    return count;
  }

 private:
  void initialize_buckets(size_type n) {
    size_type n_buckets = next_size(n);
    buckets.reserve(n_buckets);
    buckets.insert(buckets.end(), n_buckets, 0);
    num_elements = 0;
  }

  size_type next_size(size_type n) const { return __next_prime(n); }

  std::pair<iterator, bool> insert_unique_noresize(const_reference obj) {
    const size_type n = bkt_num(obj);
    node *first = buckets[n];

    for (node *cur = first; cur; cur = cur->next)
      if (equals(get_key(cur->val), get_key(obj)))
        return std::pair<iterator, bool>{iterator{cur, this}, false};

    node *tmp = new_node(obj);
    tmp->next = buckets[n];
    buckets[n] = tmp;
    ++num_elements;
    return std::pair<iterator, bool>{iterator{tmp, this}, true};
  }

  iterator insert_equal_noresize(const_reference obj) {
    const size_type n = bkt_num(obj);
    node *first = buckets[n];

    for (node *cur = first; cur; cur = cur->next) {
      if (equals(get_key(cur->val), get_key(obj))) {
        node *tmp = new_node(obj);
        tmp->next = cur->next;
        cur->next = tmp;
        ++num_elements;
        return iterator{tmp, this};
      }
    }

    node *tmp = new_node(obj);
    tmp->next = first;
    buckets[n] = tmp;
    ++num_elements;
    return iterator{tmp, this};
  }

  size_type bkt_num(const_reference val, size_type n) const {
    return bkt_num_key(get_key(val), n);
  }

  size_type bkt_num(const_reference val) const {
    return bkt_num_key(get_key(val), buckets.size());
  }

  size_type bkt_num_key(const key_type &key) const {
    return bkt_num_key(key, buckets.size());
  }

  size_type bkt_num_key(const key_type &key, size_type n) const {
    return hash(key) % n;
  }

  node *new_node(const_reference obj) {
    node *p = Alloc::allocate(1);
    p->next = 0;
    try {
      ezstl::construct(&p->val, obj);
    } catch (...) {
      Alloc::deallocate(p);
      throw;
    }
    return p;
  }

  void delete_node(node *p) {
    ezstl::destroy(p);
    Alloc::deallocate(p);
  }

  friend iterator;
  friend const_iterator;
};

}  // namespace ezstl